//
//  105. 从前序与中序遍历序列构造二叉树.swift
//  Top600
//
//  Created by rjb on 2021/7/29.
//

import Foundation
class Solution105 {
    // 从前序遍历 与 中序遍历中构建二叉树
    // 中序遍历定范围
    // 前序遍历定根
    // 采用递归的方式
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
       return buildSubTree(preorder: preorder, inorder: inorder, preStart: 0, preEnd: preorder.count - 1, inStart: 0, inEnd: inorder.count - 1)
    }
    
    func buildSubTree(preorder: [Int],
                      inorder: [Int],
                      preStart: Int,
                      preEnd: Int,
                      inStart: Int,
                      inEnd: Int) -> TreeNode?{
        if preStart > preEnd {
            return nil
        }
        if inStart > inEnd {
            return nil
        }
        let cur = preorder[preStart]
        let node = TreeNode(cur)
        
        var length = 0
        var inOrderEnd = inEnd
        for index in inStart..<inorder.count {
            let value = inorder[index]
            // 找到了根节点
            if value == cur {
                length = index - inStart
                inOrderEnd = index
                break
            }
        }
       
        // 左边
        node.left = buildSubTree(preorder: preorder,
                                 inorder: inorder,
                                 preStart: preStart + 1,
                                 preEnd: preStart + length,
                                 inStart: inStart,
                                 inEnd: inOrderEnd - 1)
        // 右边
        node.right = buildSubTree(preorder: preorder,
                                  inorder: inorder,
                                  preStart: preStart + length + 1,
                                  preEnd: preEnd,
                                  inStart: inOrderEnd + 1,
                                  inEnd: inEnd)
        return node
    }
    static func test() {
        let solution = Solution105()
        let preOrder = [3,9,20,15,7]
        let inOrder = [9,3,15,20,7]
        let result = solution.buildTree(preOrder, inOrder)
        print(result)
    }
}
